package nowCoder;

public class GetMinSortLength {
	/**
	 *	求需要排序的最短子数组长度
	 *	输入：数组arr
	 *	返回：需要排序的最短子数组长度
	 */
	public int getMinSortLength(int[] arr) {
		if(arr==null || arr.length==0)
			return 0;
		int stackPoint = 0;
		int leftBound = 0,rightBound = 0;
		int i=0;
		while(i<arr.length && arr[i]>=arr[stackPoint]){
			stackPoint = i;
			i++;
		}
		while(i<arr.length){
			while(stackPoint>=0 && arr[i]<arr[stackPoint]){
				stackPoint--;
			}
			i++;
			
		} 
		if(stackPoint==arr.length-1)
			return 0;
		leftBound = stackPoint+1;
		
		
		stackPoint = arr.length-1;
		i=arr.length-1;
		while(i>=0 && arr[i]<=arr[stackPoint]){
			stackPoint = i;
			i--;
		}
		while(i>=0){
			while(stackPoint<arr.length && arr[i]>arr[stackPoint])
				stackPoint++;
			i--;
			
		}
		rightBound = stackPoint-1;
		return rightBound-leftBound+1;
	}
	public static void main(String[] args){
		GetMinSortLength getMinSortLength = new GetMinSortLength();
		int[] arr = {1,2,3,5,4,7,6,9,9,9};
		System.out.println(getMinSortLength.getMinSortLength(arr));
	}
}
